home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / inet / ien / ien-179 < prev    next >
Text File  |  1988-12-01  |  10KB  |  208 lines
  1.  
  2.  
  3. IEN-179
  4.                                                         March 11th, 1981
  5.                                                              Danny Cohen
  6.                                                                USC / ISI
  7.  
  8.                          Addressing and Routing
  9.                          ----------------------
  10.  
  11. There  are  several  approaches  to  addressing such as hierarchical and
  12. flat, but there is only one approach to routing:  Take the best (usually
  13. the shortest) path.
  14.  
  15. The choice of addressing scheme which is both manageable and may support
  16. an efficient routing is the subject of this note.
  17.  
  18. Hierarchical addressing is probably the easiest to manage.  The universe
  19. is divided into some small  number  of  units,  and  each  of  which  is
  20. assigned  an  address  which is some kind of a string, typically numeric
  21. but not necessarily so.
  22.  
  23. If any of these units contains  more  than  one  member  then  the  same
  24. process  is repeated (iterated).  The address of the subunit is appended
  25. somehow, typically to the end  (but  sometimes  to  the  front)  of  the
  26. address of the parent unit.
  27.  
  28. This  hierarchy  is  easy  to  manage  such  that addresses are uniquely
  29. assigned.
  30.  
  31. Typically in an hierarchy each unit is  capable  of  communicating  both
  32. with its ancestor and with all of its immediate descendants.
  33.  
  34. A  default  routing  can  always  be easily derived from an hierarchical
  35. address.  This route consists of going up to a common ancestor  (parent)
  36. and then down to the destination.
  37.  
  38. Hence,  an  hierarchical  address is always a route from the root (sorry
  39. about that).
  40.  
  41. This  default routing requires only N-1 communication links which is the
  42. minimal connectivity for N nodes.
  43.  
  44. In this situation the default route is also the only existing route,  up
  45. to trivial changes.
  46.  
  47. In  reality,  for  efficiency  reasons,  the connectivity is richer than
  48. that.  Typically, brothers are in  direct  communication,  and  a  "top"
  49. (root) may not exist at all.
  50.  
  51. IEN-179                                                         [Page 2]
  52.  
  53.  
  54.  
  55. Because  of the connectivity richness the routing process is non-trivial
  56. and requires that decisions be made.
  57.  
  58. Routing is the process of chosing a possible communication  link,  where
  59. there is more than one.
  60.  
  61. The  other  extreme  of  addressing  is  the  flat  space approach where
  62. locations have totally random dependency  on  their  addresses,  meaning
  63. that  a  fully instantiated table lookup must be used in order to locate
  64. an address.
  65.  
  66. The important feature of flat and  random  addressing  is  that  it  can
  67. conveniently support mobile users.
  68.  
  69. A  simple,  however  expensive,  way  for implementing routing when flat
  70. addressing is used is by  providing  all  the  switches  (where  routing
  71. decisions  have  to  be  made)  with  tables containing all the required
  72. information about all the addresses.
  73.  
  74. In the case of flat addressing it is  required  that  all  addresses  be
  75. globally unique.  It is not required however that all addresses be known
  76. to  all  the  switching nodes, provided that nodes can ask for, and get,
  77. information about addresses which were not known to them.
  78.  
  79. In the hierarchical case it is possible either  that  all  addresses  be
  80. specified  in  an  absolute  (complete)  mode or in a relative (partial)
  81. mode.  The former requires that all addresses  be  fully  expanded,  and
  82. have  the  same  format  regardless  of  where they are specified (e.g.,
  83. 1-213-822-1511x104), and the  latter  supports  short  forms  for  local
  84. addresses, at the possible expense of additional control information for
  85. remote addresses.  The same address shown before may be specified as 104
  86. from  inside  ISI  as 822-1511x104 from the STN at LA, as 9-822-1511x104
  87. from   UCLA,   as   213-822-1511x104    from    Palo    Alto    or    as
  88. 010-1-213-822-1511x104  from  London.   Similarly, intra-office memos do
  89. not require long addresses, and intra-country mail does not require  the
  90. country name to be specified in the address.
  91.  
  92. Any  system which can handle perfectly flat addresses can take advantage
  93. of rich communication connectivity  and  can  also  handle  multi-homing
  94. (destination with more than one address).
  95.  
  96. An   hierarchical   addressing   scheme  which  uses  only  the  default
  97. hierarchical  routing may have difficulties in handling efficiently rich
  98. connectivity and multi-homing.
  99.  
  100. However, between these two extremes there is a wide  spectrum  of  other
  101. possibilities.
  102.  
  103. The  claim  of the rest of this paper is that (i) hierarchical addresses
  104. are easier to manage, and (ii) if you can handle flat  addresses  -  you
  105. can handle hierarchical addresses even better.
  106.  
  107. IEN-179                                                         [Page 3]
  108.  
  109.  
  110.  
  111. Hierarchical addressing is at least as good (in any respect) as flat one
  112. because  flat  addressing  is a special case of hierarchical addressing,
  113. but not the other way round.
  114.  
  115. Suppose that  there  is  a  system  which  can  handle  very  well  flat
  116. addressing.   Since the only requirement for the flat addressing is that
  117. addresses are unique, one can assign unique addresses in  any  way,  for
  118. example  in  a very structured way, like hierarchical.  The introduction
  119. of hierarchical addresses to  the  flat  addressing  scheme  should  not
  120. degrade its performance since the uniqueness was not disturbed.
  121.  
  122. Suppose  further  that  all  the addresses are examined at every switch.
  123. All addresses which result in the same routing  decisions  by  both  the
  124. flat  addressing  scheme  and by the hierarchical addressing are marked,
  125. and the  entries  corresponding  to  them  are  removed  from  the  flat
  126. addressing tables.
  127.  
  128. This  causes  no  degradation  of  the flat addressing scheme (which was
  129. assumed to  be  a  good  one  to  start  with)  since  the  hierarchical
  130. addressing  yields  the same routing decision for these addresses.  This
  131. process repeats at all levels, and only the "GCD" addresses are stored.
  132.  
  133. Hence, after removing these addresses the size of the  tables  decreases
  134. in  all  switches  which probably may yield some performance improvement
  135. and increased capacities.  In fact,  the  resulting  scheme  is  now  an
  136. hierarchical  scheme  with tables of exceptions which are handled in the
  137. best known way.  The format of the exception table is discussed later.
  138.  
  139. Note that this results in uneven distribution of knowledge. At different
  140. switches different set of destinations are known.  For example, all  the
  141. traffic  to the East coast may be treated in the same way when being far
  142. away from there, but as the message approaches its  destination,  it  is
  143. likely that the granularity of the address examination changes such that
  144. more  details are used.  When leaving Tokyo the only part of the address
  145. which was used for  the  routing  was  the  fact  that  the  message  is
  146. addressed  to  the  States.  After  arriving  at  California, the Boston
  147. traffic may be treated separately from the Washington traffic, later the
  148. Boston traffic is examined even closer to distinguish the Cambridge from
  149. the Lexington traffic, and later the MIT traffic is  isolated  from  the
  150. Harvard  and  the  BBN  traffic. Upon entering MIT the traffic is sorted
  151. further to the appropriate local MIT net,  and  later  to  its  terminal
  152. destination.
  153.  
  154. This  scheme allows the switches in Tokyo NOT to know about the internal
  155. structure of the addressing  in  the  USA  in  general  and  at  MIT  in
  156. particular.  It  also helps the switches in California to take advantage
  157. of special HU (high utilization) trunks to the Boston area, if any.
  158.  
  159. Since  this  hybrid  contains  both  the  flat  and   the   hierarchical
  160. addressing, multi homing can be handled as well as by flat addressing.
  161.  
  162. IEN-179                                                         [Page 4]
  163.  
  164.  
  165.  
  166. Another  variant of this scheme is not to start with full tables of flat
  167. addresses (which are impossible to manage) but to treat the system as if
  168. it was a pure hierarchical one, but in addition to maintain a  table  of
  169. exception which is dynamically updated.
  170.  
  171. The  entries  in  these  exception tables should include both addresses,
  172. their granularity level and the associated routing decision.    If,  for
  173. example,  addresses  always consist of a sequence of bytes (of any size)
  174. the granularity level may be measured by the number of bytes  which  are
  175. used.
  176.  
  177. For  example,  a  telephone exchange in Marina del Rey may know that the
  178. traffic for 1-213-828X and 1-213-821X is  local,  all  the  traffic  for
  179. addresses  2X  and 4X (Europe) should be routed to a certain cable which
  180. goes directly to Europe, the traffic to 1-212X be routed to a some cable
  181. which goes directly to NY, the traffic to either 1-617-49X or 1-617-253X
  182. should be routed to the HU trunk which goes to Cambridge, and  similarly
  183. the traffic to 1-202-694-3049 should be given to a certain line which is
  184. connected  to  a  certain  destination,  somewhere.  All the rest of the
  185. traffic should be routed to downtown  LA  where  smarter  computers  can
  186. solve the routing.
  187.  
  188. In  the  above  example  the  various  entries  have different levels of
  189. granularity, varying from 1 (in the case of Europe) to 11 (in  the  last
  190. example).
  191.  
  192. Such  a  scheme  yields  tables of reasonable size, can benefit from any
  193. structure  and  logic/regularity  (as  opposed  to  randomness)  of  the
  194. communication  subsystem, can handle multihoming, and has the capability
  195. to utilize special irregular HU lines and shortcuts.
  196.  
  197. Note that in this scheme the addressing may be highly structured  (e.g.,
  198. in  a  hierarchical  way)  but  the  routing is not necessarily so.  The
  199. routing is hierarchical only when this is known to be the  right  thing,
  200. or  when nothing else is known and the hierarchical routing is used as a
  201. default.
  202.  
  203. In summary, this is a way to benefit from the simplicity of hierarchical
  204. routing whenever possible, while being able to use  the  flat-addressing
  205. features  when  needed,  on  a  case-by-case  basis, without the need to
  206. maintain tables of unreasonable size.
  207.  
  208.